//排序和搜索
{

    class ArryList {

        constructor() {

            this.array = [];

        }

        insert(item) {
            this.array.push(item);
        }

        toString() {
            return this.array.join();
        }
    }

    class Tool {

        constructor() {}

        swap(array, index_1, index_2) {
            [array[index_1], array[index_2]] = [array[index_2], array[index_1]];
        }

        //基础冒泡排序
        bubbleSort(array) {

            let length = array.length;

            // for(let i=0;i<length;i++){
            //     for(let j=0;j<length-1;j++ ){
            //         if(array[j] > array[j+1]){
            //             this.swap(array,j,j+1);
            //         }
            //     }
            // }

            //优化的冒泡排序
            for (let i = 0; i < length; i++) {

                for (let j = 0; j < length - i - 1; j++) {

                    if (array[j] > array[j + 1]) {

                        this.swap(array, j, j + 1);
                    }

                }
            }
        }

        //选择排序
        selectSort(array) {

            let length = array.length,
                indexMin;

            for (let i = 0; i < length - 1; i++) {
                indexMin = i;
                for (let j = i + 1; j < length; j++) {
                    if (array[indexMin] > array[j]) {
                        indexMin = j;
                    }
                }

                [array[i], array[indexMin]] = [array[indexMin], array[i]]
            }
        }

        //插入排序

        insertSort(arr) {

            let length = arr.length,
                j,
                temp;

            for (let i = 1; i < length; i++) {

                j = i;
                temp = arr[j];

                while (j > 0 && arr[j - 1] > temp) {

                    arr[j] = arr[j - 1];

                    j--;

                }
                arr[j] = temp;
            }
        }
    }


    let arrList = new ArryList();
    let tools = new Tool();

    for (let i = 0; i < 8; i++) {
        arrList.insert((Math.random() * 10).toFixed(0));
    }

    console.log(arrList.toString());
    // tools.bubbleSort(arrList.array);
    // tools.selectSort(arrList.array);
    tools.insertSort(arrList.array)
    console.log(arrList.toString());
}


// 并归排序
{
    function merge(left, right) {
        var result = [];
        while (left.length > 0 && right.length > 0) {
            if (left[0] < right[0]) {
                result.push(left.shift());
            } else {
                result.push(right.shift());
            }
        }
        /* 当左右数组长度不等.将比较完后剩下的数组项链接起来即可 */
        return result.concat(left).concat(right);
    }

    function mergeSort(arr) {
        if (arr.length == 1) {
            return arr
        };
        var mid = Math.floor(arr.length / 2);
        var left_arr = arr.slice(0, mid),
            right_arr = arr.slice(mid);
        return merge(mergeSort(left_arr), mergeSort(right_arr));
    }

    var arr = [12, 20, 30, 21, 15, 33, 26, 19, 40, 25];

    console.log('----并归排序----');
    console.log(mergeSort(arr).toString());

}

//快速排序
{
    let times = 0;
    function quickSort(arr) {
        
        //如果数组长度小于等于1无需判断直接返回即可
        if(arr.length<=1){
            return arr;
        }
        let midIndex=Math.floor(arr.length/2);//取基准点
        let midIndexVal=arr.splice(midIndex,1);//取基准点的值,splice(index,1)函数可以返回数组中被删除的那个数arr[index+1]
        
        let left=[];//存放比基准点小的数组
        let right=[];//存放比基准点大的数组
        
        //遍历数组，进行判断分配
        for(let i=0;i<arr.length;i++){
            if(arr[i]<midIndexVal){
                left.push(arr[i]);//比基准点小的放在左边数组
            }
            else{
                right.push(arr[i]);//比基准点大的放在右边数组
            }
            console.log("第"+(++times)+"次排序后："+arr);
        }
        //递归执行以上操作,对左右两个数组进行操作，直到数组长度为<=1；
        return quickSort(left).concat(midIndexVal,quickSort(right));
    

    }

    let _arr = [12, 20, 30, 21, 15, 33, 26, 19, 40, 25];

    console.log('----快速排序----');
    console.log(quickSort(_arr));



}